#include <stdio.h>
#include <stdlib.h>

static int compare(const void *a, const void *b)
{
	return *(int *)a - *(int *)b;
}

static void two_sum(int *nums, int start, int end, int target, int **results, int *count)
{
	int low = start;
	int high = end;
	while (low < high) {
		while (low > start && nums[low] == nums[low - 1])
		{
			low++;
		}
		while (high < end && nums[high] == nums[high + 1])
		{
			high--;
		}
		if (low >= high) break;
		int sum = nums[low] + nums[high];
		if (sum < target) {
			low++;
		}
		else if (sum > target) {
			high--;
		}
		else {
			results[*count] = malloc(3 * sizeof(int));
			results[*count][0] = -target;
			results[*count][1] = nums[low];
			results[*count][2] = nums[high];
			(*count)++;
			//while (++low < high && nums[low] == nums[low - 1]) {}
			//while (--high > low && nums[high] == nums[high + 1]) {}
			low++;
			high--;
		}
	}
}

int** threeSum(int* nums, int numsSize, int* returnSize)
{
	if (numsSize < 3) {
		return NULL;
	}

	qsort(nums, numsSize, sizeof(*nums), compare);

	int i, j, capacity = 50000;
	int **results = (int **)malloc(capacity * sizeof(int *));
	for (i = 0; i < numsSize - 2; i++) 
	{
		if (i == 0 || i > 0 && nums[i] != nums[i - 1]) {
			two_sum(nums, i + 1, numsSize - 1, -nums[i], results, returnSize);
		}
	}
	return results;
}
int main(void)
{
	int i, count=0;
	int nums[] = { -2,0,0,2,2 };
	int **triplets = threeSum(nums, sizeof(nums) / sizeof(*nums), &count);
	for (i = 0; i < count; i++) {
		printf("%d %d %d\n", triplets[i][0], triplets[i][1], triplets[i][2]);
	}
	system("pause");
	return 0;
}